//
// Created by Lenovo on 2021/12/15.
//

#include "Linear_SingleLinkList.h"


Status ListInit(LinkList* L){
    ElemType* po= CreatElem(0);//初始化头节点的数据
    if(!po) exit(ERROR);
    LNode* head = (LNode*) malloc(sizeof(LNode));//初始化头节点数据
    if(!head) exit(ERROR);
    head->data=po;
    head->next=NULL;
    L->head=head;//初始化链表
    L->tail=head;
    L->ListSize=0;

    return OK;
}

Status DestroyList(LinkList* L){
    //如果链表本身为空或者内容为空
    if(L==NULL||L->head==NULL) return ERROR;

    ClearList(L);//先清空链表
    free(L->head);//释放头节点
    L->head=NULL;//释放后置空
    L->tail=NULL;
    free(L);//释放链表空间
    L=NULL;
    return OK;
}

Status ClearList(LinkList* L){
    //判断链表合法性
    if(L==NULL||L->head==NULL) return ERROR;
    //判断链表是否为空
    if(L->head->next==NULL) return OK;

    //释放链表空间
    LNode * P = L->head->next;
    LNode * Ptmp;
    while (P->next!=NULL){
        Ptmp=P;
        P=P->next;
        free(Ptmp);
        Ptmp=NULL;
    }
    //初始化
    L->tail=L->head;
    L->ListSize=0;

    return OK;
}

Status InsertFirst(LinkList* L,LNode s){
    if(L==NULL||L->head==NULL)    return ERROR;

    //创造要插入的结点空间并判断合法性
    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    //初始化结点数据
    po->next=NULL;
    po->data=s.data;

    //插入结点
    po->next=L->head->next;
    L->head->next=po;
    L->ListSize++;

    return OK;
}

LNode DestroyFirst(LinkList* L){
    //判断是否为空
    if(L==NULL||L->head->next==NULL||L->head==NULL) exit(ERROR);

    LNode* Ptmp=L->head->next;//保存要销毁的结点的地址
    LNode tmp;
    LNodeInit(&tmp);
    tmp.next=Ptmp->next;
    tmp.data=Ptmp->data;
    L->head->next=L->head->next->next;//将头节点的指向改变

    free(Ptmp);
    Ptmp=NULL;
    L->ListSize--;

    return tmp;
}

Status Append(LinkList* LH,LinkList* LT){
    //判断两链表的合法性
    if(LH==NULL||LT==NULL||LH->head==NULL||LT->head==NULL)  return ERROR;
    //链表连接
    LH->tail->next=LT->head->next;
    LH->tail=LT->tail;
    LH->ListSize+=LT->ListSize;
    return OK;
}

LNode RemoveTail(LinkList* L){
    if(L==NULL||L->head==NULL) exit(ERROR);

    //获取及保存尾节点位置与内容
    LNode *Ptmp,re;
    LNodeInit(&re);
    Ptmp=L->tail;
    re.next=Ptmp->next;
    re.data=Ptmp->data;

    //获取尾节点的上一个结点
    LNode * tmp=L->head;
    LNode * ptmp=L->tail;
    while (tmp->next!=L->tail){
        tmp=tmp->next;
    }
    //链表尾节点位置重置
    L->tail=tmp;
    L->tail->next=NULL;
    //原尾节点释放
    free(ptmp);
    ptmp=NULL;
    L->ListSize--;

    return re;
}

Status InsertBefore(LinkList* L,LNode* p,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;

    //获取指定结点的上一个结点
    LNode * tmp=L->head;
    while (tmp->next!=p&&tmp->next!=NULL){
        tmp=tmp->next;
    }
    //如果指定结点不存在
    if(tmp->next==NULL) {
        printf("\np None Exist\n");
        return ERROR;
    }

    //为新结点开辟空间和初始化数据
    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->data=s.data;

    //插入结点
    po->next=tmp->next;
    tmp->next=po;
    L->ListSize++;

    return OK;
}

Status InsertAfter(LinkList* L,LNode* p,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;

    //获取指定结点上一个结点位置
    LNode * tmp=L->head->next;
    while (tmp!=p&&tmp!=NULL){
        tmp=tmp->next;
    }
    //如果指定结点不存在
    if(tmp==NULL) {
        printf("\np none exist\n");
        return ERROR;
    }

    //为新节点开辟空间与初始化数据
    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->data=s.data;

    //插入结点
    po->next=tmp->next;
    tmp->next=po;
    L->ListSize++;

    return OK;
}

Status SetCurElem(LNode* p,ElemType e){
    *(p->data)=e;
    return OK;
}

ElemType GetCurElem(LNode p){
    return *p.data;
}

Status ListEmpty(LinkList L){
    if(L.head==NULL)    return ERROR;

    //如果链表结点为0，则为空（个人觉得此方法判断不安全）
    if(L.ListSize==0) return ERROR;
    else if(L.ListSize==1){
        return TRUE;
    } else
        return FALSE;
}

int ListLength(LinkList L){
    if(L.head== NULL)   return ERROR;

    return L.ListSize;
}

LNode* GetHead(LinkList L){
    if(L.head==NULL) exit(ERROR);
    return L.head->next;
}

LNode* GetLast(LinkList L){
    if(L.head==NULL) exit(ERROR);
    return L.tail;
}

LNode* PriorPos(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;
    if(p==L.head->next) return NULL;

    //获取指定结点的前一个结点
    LNode * tmp=L.head->next;
    while (tmp->next!=p&&tmp->next!=NULL){
        tmp=tmp->next;
    }
    if(tmp==L.tail) return NULL;
    return tmp;
}

LNode* NextPos(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;
    if(p==L.tail)   return NULL;

    //获取指定结点的下一个结点
    LNode * tmp=L.head->next;
    while (tmp!=p&&tmp!=NULL){
        tmp=tmp->next;
    }
    return tmp->next;
}

LNode* LocatePos(LinkList L,int i){
    if(L.head==NULL) exit(ERROR);

    //判断位置是否合法
    if(i<1||i>L.ListSize){
        printf("\ni is illegal!(1<=i<=%d)\n", L.ListSize);
    }
    //获取指定位置结点
    LNode * tmp=L.head->next;
    int j=1;
    while (j<i){
        tmp=tmp->next;
        j++;
    }

    return tmp;
}

LNode* LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType)){
    if(L.head==NULL)    return NULL;

    //获取指定元素位置
    LNode * tmp=L.head->next;
    while (tmp!=NULL){
        //判断是否为该元素的函数（用户自定义，函数指针）
        if((*compare)(*tmp->data,e)){
            return tmp;
        }
        tmp=tmp->next;
    }
    return NULL;
}

Status ListTraverse(LinkList L,Status (*visit)(LNode* )){
    if(L.head==NULL||L.ListSize==0)    return ERROR;

    LNode* tmp=L.head->next;
    if(tmp==NULL)
        return EMPTY;
    //链表遍历
    while (tmp!=NULL){
        //visit函数指针，函数用户自定义
        (*visit)(tmp);
        tmp=tmp->next;
    }
    return OK;
}

Status ListInsert_L(LinkList* L,int i,LNode s){

    if(L==NULL||L->head==NULL) return ERROR;
    //判断i是否合法
    if(i<1||i>L->ListSize){
        printf("\nThe number is illegal!\n");
        return ERROR;
    }

    //确定指定结点位置
    LNode* tmp=L->head;
    int j=0;
    while (j<i-1){
        tmp=tmp->next;
        j++;
    }

    //结点创建与插入
    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->data=s.data;

    po->next=tmp->next;
    tmp->next=po;


    return OK;
}

Status ListPushHead(LinkList* L,LNode s){
    if(L==NULL||L->head==NULL)  return ERROR;

    //为新结点开辟空间
    LNode * po=(LNode*) malloc(sizeof(LNode));
    if(!po) return ERROR;
    po->next=NULL;
    po->data=s.data;

    //插入新结点
    if(L->tail==L->head){
        L->head->next=po;
        L->tail=po;
    } else{
        po->next=L->head->next;
        L->head->next=po;
    }
    L->ListSize++;
    return OK;
}

Status LNodeInit(LNode* l){
    //结点初始化
    l=(LNode *)malloc(sizeof(LNode));
    l->next=NULL;
    l->data= CreatElem(0);
    return OK;
}

ElemType* CreatElem(int data){
    //数据结点初始化
    ElemType* po=(ElemType*) malloc(sizeof(ElemType));
    *po=data;
    return po;
}


Status List_Sort(LinkList* L,Status (*compare)(ElemType e,ElemType f)){
    if(L==NULL||L->head==NULL)
        return ERROR;
    LNode* tmp=L->head->next;
    if(tmp==NULL)
        return EMPTY;
    //思想姐u是冒泡排序的思想
    while (tmp!=NULL){
        LNode* j=tmp->next;
        while(j!=NULL){
            if((*compare)(*tmp->data,*j->data)){
                //整个结点交换，但不适用（不会）
//                LNode *Ptmp= PriorPos(*L,tmp),*Jtmp= PriorPos(*L,j),*Jnext=j->next;
//                Ptmp->next=j;
//                Jtmp->next=tmp;
//                j->next=tmp->next;
//                tmp->next=Jnext;
                //数据交换，结点地址不交换
                ElemType *Tdata= tmp->data;
                tmp->data=j->data;
                j->data=Tdata;
            }
            j=j->next;
        }
        tmp=tmp->next;
    }

    return OK;
}

LNode* PriorPosForSelectSort(LinkList L,LNode* p){
    if(L.head==NULL)    return NULL;


    LNode * tmp=L.head->next;
    while (tmp->next!=p&&tmp->next!=NULL){
        tmp=tmp->next;
    }
    if(tmp==L.tail) return NULL;
    return tmp;
}

Status ListSelectSort(LinkList* L,Status (*compare)(ElemType e,ElemType f)){
    if(L==NULL||L->head==NULL)
        return ERROR;
    if(L->head->next==NULL)
        return EMPTY;

    LNode * r=L->head,*min=L->head->next;

    while (min->next!=NULL){
        LNode * tmp=r->next;
        while (tmp!=NULL){
            if((*compare)(*tmp->data,*min->data)){
                min=tmp;
            }
            tmp=tmp->next;
        }
        LNode *pNext=r->next;
        PriorPosForSelectSort(*L,min)->next=min->next;
        r->next=min;
        min->next=pNext;
        r=min;
        min=r->next;
    }

    return OK;
}


Status ListRevers(LinkList* L){
    if(L==NULL||L->head==NULL)  return ERROR;

    //双辅助结点交换逆置
    L->tail=L->head->next;
    LNode* Ptmp=L->head->next;
    LNode *p=NULL,*q;
    while (Ptmp!=NULL){
        q=Ptmp->next;
        Ptmp->next=p;
        p=Ptmp;
        Ptmp=q;
    }
    L->head->next=p;
    return OK;
}





